package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/'>找出美丽数组的最小和(Find the Minimum Possible Sum of a Beautiful Array)</a>
 * <p>给你两个正整数：n 和 target 。</p>
 * <p>
 * 如果数组 nums 满足下述条件，则称其为 美丽数组 。
 *     <ul>
 *         <li>nums.length == n.</li>
 *         <li>nums 由两两互不相同的正整数组成。</li>
 *         <li>在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。</li>
 *     </ul>
 * </p>
 * <p>返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 10^9 + 7。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：n = 2, target = 3
 *      输出：4
 *      解释：nums = [1,3] 是美丽数组。
 *          - nums 的长度为 n = 2 。
 *          - nums 由两两互不相同的正整数组成。
 *          - 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
 *          可以证明 4 是符合条件的美丽数组所可能具备的最小和。
 *
 * 示例 2：
 *      输入：n = 3, target = 3
 *      输出：8
 *      解释：
 *          nums = [1,3,4] 是美丽数组。
 *          - nums 的长度为 n = 3 。
 *          - nums 由两两互不相同的正整数组成。
 *          - 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
 *          可以证明 8 是符合条件的美丽数组所可能具备的最小和。
 *
 * 示例 3：
 *      输入：n = 1, target = 1
 *      输出：1
 *      解释：nums = [1] 是美丽数组。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= n <= 10^9</li>
 *      <li>1 <= target <= 10^9</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/8 9:25
 */
public class LC2834FindMinimumPossibleSumOfBeautifulArray_M {
    static class Solution {
        public int minimumPossibleSum(int n, int target) {
            final int MOD = (int) 1e9 + 7;
            // m = target的一半。即 target = 2*m 或者 target = 2*m + 1
            int m = target / 2;
            // 如果 n<=m，那么最大值为：n + (n-1) = 2 * n - 1；2 * n - 1<=2*m-1，一定小于target
            if (n <= m) {
                return (int) ((long) (1 + n) * n / 2 % MOD);
            }
            // 如果超过的话，前半段仍为 1,2,3,...,m-1,m；后半段必须从target开始
            // 否则比target小的任何数与前半段的某个值相加都会等于target
            // 使用等差数列求和
            return (int) (((long) (1 + m) * m / 2 + ((long) target + target + (n - m) - 1) * (n - m) / 2) % MOD);
        }
    }
}
